home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / decomp / decision.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  10.0 KB  |  462 lines
  1. # include    <ingres.h>
  2. # include    <symbol.h>
  3. # include    <aux.h>
  4. # include    <tree.h>
  5. # include    "globs.h"
  6. # include    <sccs.h>
  7.  
  8. SCCSID(@(#)decision.c    8.1    12/31/84)
  9.  
  10. /*
  11. ** DECISION -- This file contains code related to deciding how to
  12. **    process the remaining query. The main routine is decision()
  13. **    and the other routines are called only by decision. The routine
  14. **    in this file include:
  15. **
  16. **    Decision -- Decides how to process a query.
  17. **
  18. **    Fixtl     -- Determines the target list for each component.
  19. **
  20. **    Fixresult -- Determines the result relation for the next query
  21. **
  22. **    Fixrange  -- Adjust the range table after a query
  23. **
  24. **    Fixovlap  -- Fixes trees in cases where reduction is used
  25. **
  26. **    Rmovlap   -- Restores trees in cases where reduction was used.
  27. **
  28. **    Listcomp  -- Debugging routine.
  29. */
  30. /*
  31. **    Decision is given a subquery and decides how to process it.
  32. **    The choices are:
  33. **        Disjoint pieces -- The original query had disjoint components.
  34. **                    Do each component separately.
  35. **        Reduction       -- The query is joined by a single variable.
  36. **                    Reduce the query on that joining variable
  37. **                    and do each component separately.
  38. **        Substitution    -- The query is neither disjoint nor reducible.
  39. **                    Process by tuple substitution.
  40. **
  41. **    Notice that decision() is recursive and will call itself on each
  42. **    subcomponent it decides to do. Decision calls various support
  43. **    routines in the file "reduction.c".
  44. */
  45.  
  46. decision(root, qmode, result_num, buf)
  47. QTREE    *root;
  48. int    qmode;
  49. int    result_num;
  50. char    *buf;
  51. {
  52.     register QTREE        **qp;
  53.     register struct complist *clist;
  54.     register int        ovlapvar;
  55.     struct complist        *cp;
  56.     int            i, onepiece, qtrue, map;
  57.     int            mark, mark1, cand_map;
  58.     QTREE            *tree, *newtree;
  59.     QTREE            *qlist[MAXRANGE];
  60.     int            newqmode;
  61.     int            ovlaprelnum, newr;
  62.     int            locrange[MAXRANGE];
  63.     extern QTREE        *copy_ands();
  64.     extern struct complist    *buildlist(), *order();
  65.     extern QTREE        *construct();
  66.  
  67. #    ifdef xDTR1
  68.     if (tTf(37, -1))
  69.     {
  70.         printf("DECISION root=%x,vc=%d,res=%d\n", root, root->sym.value.sym_root.tvarc, result_num);
  71.     }
  72. #    endif
  73.     mark = markbuf(buf);
  74.     if (root->sym.value.sym_root.tvarc < 3)
  75.     {
  76.         /* setup to do as one single piece */
  77.         onepiece = TRUE;
  78.     }
  79.     else
  80.     {
  81.         /* break the query apart if possible */
  82.  
  83.         /* build component list */
  84.         clist = buildlist(root, buf);
  85. #        ifdef xDTR1
  86.         if (tTf(37, 2))
  87.             listcomp(clist, "Original Comp");
  88. #        endif
  89.  
  90.         /* is query completely connected or disjoint */
  91.         map = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
  92.         onepiece = algorithm(clist, map);
  93. #        ifdef xDTR1
  94.         if (tTf(37, 1))
  95.             printf("Orig query %s\n", onepiece ? "connected" : "disjoint");
  96. #        endif
  97.         /* assume there is no joining variable */
  98.         ovlapvar = -1;
  99.  
  100.         if (onepiece)
  101.         {
  102.             /*
  103.             ** Try to reduce a single connected piece.
  104.             ** In turn each variable will be logically
  105.             ** removed from the query and a test will
  106.             ** be made to see if the query is still
  107.             ** connected.
  108.             */
  109.  
  110.             cand_map = map;
  111.             for (i = 1; cand_map; i <<= 1)
  112.             {
  113.                 if ((cand_map & i) == 0)
  114.                     continue;
  115.                 cand_map &= ~i;
  116.                 freebuf(buf, mark);
  117.                 clist = buildlist(root, buf);
  118.                 if (algorithm(clist, map & ~i) == 0)
  119.                 {
  120.                     ovlapvar = bitpos(i);
  121.                     ovlaprelnum = De.de_rangev[ovlapvar].relnum;
  122.                     onepiece = FALSE;
  123.                     break;
  124.                 }
  125.             }
  126. #            ifdef xDTR1
  127.             if (tTf(37, 1))
  128.             {
  129.                 if (ovlapvar < 0)
  130.                     printf("Query not reducible\n");
  131.                 else
  132.                 {
  133.                     printf("Query Reducible on %d\n", ovlapvar);
  134.                     if (tTf(37, 3))
  135.                         listcomp(clist, "After reduct");
  136.                 }
  137.             }
  138. #            endif
  139.         }
  140.  
  141.         /*
  142.         ** If query is more than one piece, build trees
  143.         ** for each piece.
  144.         */
  145.  
  146.         if (!onepiece)
  147.         {
  148.             /* order pieces */
  149.             clist = order(clist, ovlapvar);
  150. #            ifdef xDTR1
  151.             if (tTf(37, 4))
  152.                 listcomp(clist, "After ordering");
  153. #            endif
  154.             cp = clist;
  155.             qp = qlist;
  156.             do
  157.             {
  158.                 *qp++ = construct(root, cp, buf);
  159.             } while (cp = cp->nextcomp);
  160.             *qp++ = 0;
  161.         }
  162.     }
  163.  
  164.     /*
  165.     ** The query is now either the one original piece or
  166.     ** is in multiple pieces. The information in clist
  167.     ** has been thrown away and now the ordered pieces
  168.     ** will be processed.
  169.     */
  170.  
  171.     if (onepiece)
  172.     {
  173.         freebuf(buf, mark);
  174.         qtrue = decompy(root, qmode, result_num, buf);
  175.     }
  176.     else
  177.     {
  178.         /* the query is in pieces. prepare to process */
  179.  
  180.         newquery(locrange);    /* save state of range table */
  181.  
  182.         /* determine the target list for each piece of the query */
  183.         for (qp = qlist; tree = *qp++; )
  184.             fixtl(tree, qp, ovlapvar, buf);
  185.  
  186.         /* adjust refs to ovlapvar since domain #'s could have changed */
  187.         fixovlap(qlist, ovlapvar, buf);
  188.  
  189.  
  190.         /* now process each component */
  191.         mark1 = markbuf(buf);
  192.         for (qp = qlist; tree = *qp++; )
  193.         {
  194.  
  195. #            ifdef xDTR1
  196.             if (tTf(37, 6))
  197.             {
  198.                 printf("next piece\n");
  199.                 treepr(tree);
  200.             }
  201. #            endif
  202.  
  203.             /* determine result relation name */
  204.             newr = fixresult(root, tree, &newqmode, qmode, result_num);
  205.     
  206.             /*
  207.             ** Run the query. If reduction is being
  208.             ** performed, the actual tree given to
  209.             ** the decision routine must be a copy
  210.             ** to protect from the recursive call changing
  211.             ** the tree. Any work done at this level,
  212.             ** must be to the original tree
  213.             */
  214.             newtree = tree;
  215.             if (ovlapvar != -1)
  216.             {
  217.                 freebuf(buf, mark1);
  218.                 newtree = copy_ands(tree, buf);
  219.             }
  220.             qtrue = decision(newtree, newqmode, newr, buf);
  221.     
  222.             /* fix up the range table */
  223.             fixrange(root, tree, ovlapvar, ovlaprelnum, newr);
  224.     
  225.             /* if last piece was false then done */
  226.             if (!qtrue)
  227.                 break;
  228.     
  229.         }
  230.  
  231.         /* restore the trees */
  232.         rmovlap(qlist, ovlapvar);
  233.  
  234.         /* restore range table back to original */
  235.         endquery(locrange, TRUE);    /* reopen previous range */
  236.  
  237.         /* return any buffer space used */
  238.         freebuf(buf, mark);
  239.     }
  240.  
  241.     /* all done with query */
  242.     return (qtrue);
  243. }
  244. /*
  245. ** Fixresult -- Determine result relation for "tree" query.
  246. **    If "tree" is the original target list piece then use the
  247. **        original relation and mode.
  248. **    If "tree" is a reduction piece then create a temporary relation
  249. **        for it.
  250. **    If "tree" is a disjoint piece then there is no target list nor
  251. **        result relation.
  252. **
  253. **    Return:
  254. **        result relation number
  255. **    Side Effects:
  256. **        *newmode is set to the query mode of the next piece
  257. */
  258.  
  259. fixresult(root, tree1, newmode, origmode, resnum)
  260. QTREE    *root;
  261. QTREE    *tree1;
  262. int    *newmode;
  263. int    origmode;
  264. int    resnum;
  265. {
  266.     register QTREE    *tree;
  267.     register int    newresult;
  268.  
  269.     tree = tree1;
  270.     *newmode = mdRETR;
  271.     if (tree->left->sym.type != TREE)
  272.     {
  273.         if (tree != root)
  274.         {
  275.             /* make new result for reduction step */
  276.             newresult = mak_t_rel(tree, "r", -1);
  277.         }
  278.         else
  279.         {
  280.             /* final piece with original result and mode */
  281.             newresult = resnum;
  282.             *newmode = origmode;
  283.         }
  284.     }
  285.     else
  286.         newresult = NORESULT;
  287.     return (newresult);
  288. }
  289. /*
  290. **    Update range table after a reduction has been processed.
  291. **    Only the intermediate reductions will affect the range
  292. **    table. The last piece does not.
  293. */
  294.  
  295. fixrange(root, tree, ovlapvar, reductnum, newrelnum)
  296. QTREE    *root;
  297. QTREE    *tree;
  298. int    ovlapvar;
  299. int    reductnum;
  300. int    newrelnum;
  301. {
  302.     register int    old;
  303.     register int    i;
  304.     extern DESC    *openr1();
  305.  
  306.     if (root != tree)
  307.     {
  308.         /* this is an intermediate piece */
  309.         i = ovlapvar;
  310.  
  311.         if (newrelnum >= 0)
  312.         {
  313.             old = new_range(i, newrelnum);
  314.             if (old != reductnum)
  315.                 dstr_rel(old);
  316.             openr1(i);
  317.         }
  318.     }
  319. }
  320. /*
  321. ** Fixovlap -- Adjust subsequent trees which reference the reduction var
  322. **
  323. **    If the first query in list redefines the reduction variable
  324. **    (if any) then each subsequent query which references the
  325. **    reduction variable is adjusted.
  326. **    Since there may be multiple pieces,
  327. **    subsequence redefinitions are done without
  328. **    reallocating buffer space.
  329. **
  330. */
  331.  
  332. fixovlap(qlist, ovlapvar, buf)
  333. QTREE    *qlist[];
  334. int    ovlapvar;
  335. char    *buf;
  336. {
  337.     register QTREE    **qp, *piece, **qp1;
  338.     QTREE        *next;
  339.     int        ovmap;
  340.     extern QTREE    **mksqlist();
  341.  
  342.     ovmap = 1 << ovlapvar;
  343.  
  344.     /* for each piece, if it redefines ovlapvar, then fix up rest */
  345.     for (qp = qlist; piece = *qp++; )
  346.     {
  347.         if (piece->sym.value.sym_root.lvarm & ovmap)
  348.         {
  349.             for (qp1 = qp; next = *qp1++; )
  350.             {
  351.                 if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & ovmap)
  352.                 {
  353.                     tempvar(next, mksqlist(piece, ovlapvar), buf);
  354.                     buf = NULL;    /* do not allocate on subsequent refs */
  355.                 }
  356.             }
  357.         }
  358.     }
  359. }
  360. /*
  361. ** Rmovlap -- Restore query trees back to their original state.
  362. **
  363. **    Rmovlap undoes the effect of fixovlap(). Any references
  364. **    to the reduction variable which were adjusted are now
  365. **    reverted back to the original reference. Note that the
  366. **    first piece is not effected by fixovlap.
  367. */
  368.  
  369. rmovlap(qlist, ovlapvar)
  370. QTREE    *qlist[];
  371. int    ovlapvar;
  372. {
  373.     register QTREE    **qp, *tree;
  374.     int        ovmap;
  375.  
  376.     if (ovmap = (1 << ovlapvar))
  377.     {
  378.         /* for each piece, remove any tempvars */
  379.         for (qp = &qlist[1]; tree = *qp++; )
  380.         {
  381.             origvar(tree, mksqlist(tree, ovlapvar));
  382.         }
  383.     }
  384. }
  385. /*
  386. ** Fixtl -- Determine what the target list of each tree should be.
  387. **
  388. **    Fixtl takes each query which references the reduction variable
  389. **    and looks for references to that variable in subsequent queries.
  390. **    Dfind will build a target list which includes every domain
  391. **    which will later be referenced.
  392. */
  393.  
  394. fixtl(tree1, qp1, ovlapvar, buf)
  395. QTREE    *tree1;
  396. QTREE    *qp1[];
  397. int    ovlapvar;
  398. char    *buf;
  399. {
  400.     register QTREE    *tree, **qp, *next;
  401.     int        var, map;
  402.     extern QTREE    **mksqlist();
  403.  
  404.     tree = tree1;
  405.     var = ovlapvar;
  406.     map = 1 << var;
  407.  
  408.     /*
  409.     ** if the last tree referenced the overlap variable then
  410.     ** try to fix next tree
  411.     */
  412.     if (tree->sym.value.sym_root.rvarm & map)
  413.     {
  414.         qp = qp1;
  415.         while (next = *qp++)
  416.         {
  417.             if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & map)
  418.                 dfind(next, buf, mksqlist(tree, var));
  419.         }
  420.     }
  421. }
  422.  
  423.  
  424.  
  425. # ifdef    xDTR1
  426.  
  427. /*
  428. **    This is strictly a debuggin routine used for
  429. **    printing component lists.
  430. */
  431.  
  432. listcomp(list, mesg)
  433. struct complist    *list;
  434. char        *mesg;
  435. {
  436.     register struct complist    *c, *cl;
  437.     register int            i;
  438.  
  439.     if (tTf(37, 14))
  440.     {
  441.         printf("%s\n", mesg);
  442.         i = -1;
  443.  
  444.         for (cl = list; cl; cl = cl->nextcomp)
  445.         {
  446.             i++;
  447.             printf("Component %d:map=%o\n", i, cl->bitmap);
  448.             for (c = cl; c; c = c->linkcomp)
  449.             {
  450.                 printf("%x, ", c->clause);
  451.                 if (tTf(37, 15))
  452.                 {
  453.                     treepr(c->clause->left);
  454.                     nodepr(c->clause);
  455.                 }
  456.             }
  457.             printf("\n");
  458.         }
  459.     }
  460. }
  461. # endif
  462.